|
In computer science, a binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation. ==Binomial heap== A binomial heap is implemented as a collection of binomial trees (compare with a binary heap, which has a shape of a single binary tree), which are defined recursively as follows: * A binomial tree of order 0 is a single node * A binomial tree of order ''k'' has a root node whose children are roots of binomial trees of orders ''k''−1, ''k''−2, ..., 2, 1, 0 (in this order). A binomial tree of order ''k'' has 2k nodes, height ''k''. Because of its unique structure, a binomial tree of order ''k'' can be constructed from two trees of order ''k''−1 trivially by attaching one of them as the leftmost child of the root of the other tree. This feature is central to the ''merge'' operation of a binomial heap, which is its major advantage over other conventional heaps. The name comes from the shape: a binomial tree of order has nodes at depth . (See Binomial coefficient.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Binomial heap」の詳細全文を読む スポンサード リンク
|